With the rapid advancement in Internet, packet forwarding comes to be a very important task of a router to improve quality of Internet services. Packet forwarding is a work of sending out a packet toward a final destination network using header information of the packet flowing into the router.
Requests on various kinds of services in the Internet make it further difficult to process a packet. For example, an application program such as audio or video streaming sensitive to transfer speed requests quality assurance, and a variety of services such as firewall protection, load balancing, web switching, Intrusion Detection and Security (IDS) and the like are also required. In order to provide such services, packet classification in the router should be preceded.
In packet forwarding, packets should be processed and sent out in accordance with input link speed, and it can be said that packet classification is a work more sensitive to packet processing speed since all the fields in the packet header information should be examined unlike an IP address search which simply confirms and processes only a destination address. Accordingly, studies on various packet classification structures for effectively performing packet classification are actively under progress. The most important criterion for evaluating performance of a packet classification structure is packet processing speed, and the packet processing speed is determined by the number of memory access. The second important criterion is memory size required to store a packet classification table. The required memory size depends on the data structure of the packet classification table.
Recursive flow classification (RFC) algorithm among conventional packet classification algorithms is one of the algorithms capable of classifying a packet at a high speed. However, there is a limit in practically using this algorithm since a memory use amount, a table generation time and a table size are exponentially increased according to the number of rules.
Although a lot of algorithms have been proposed thereafter, most of them have a problem in that search speed, which is the most important, is lowered in return for solving the problems of the RFC algorithm. For example, in a method proposed in a paper entitled “Scalable Packet Classification through Maximum Entropy Hashing”, IEEE/ACM Transactions on Networking, published December, 2009. a partitioning technique is used to divide an total rule set into a plurality of small sub rule sets, and if RFC tables are generated for the small sub rule sets, the size and generation time of the RFC tables are reduced greatly.
However, in order to find actually a rule corresponding to a given key, such a partitioning technique needs a process of searching for a sub rule set containing the rule, and a process of searching for an RFC table is performed after the sub rule set is found, and thus overall search performance is lowered compared with a case of simply searching for only an RFC table.
Accordingly, there is a need for a method capable of improving the search speed by reducing the number of memory access.